package com.gxc.array;

import java.util.*;

/**
 * 公元2919年，人类终于发现了一颗宜居星球——X星。
 * 现想在X星一片连绵起伏的山脉间建一个天热蓄水库，如何选取水库边界，使蓄水量最大？
 *
 * 要求：
 *
 * 山脉用正整数数组s表示，每个元素代表山脉的高度。
 * 选取山脉上两个点作为蓄水库的边界，则边界内的区域可以蓄水，蓄水量需排除山脉占用的空间
 * 蓄水量的高度为两边界的最小值。
 * 如果出现多个满足条件的边界，应选取距离最近的一组边界。
 * 输出边界下标（从0开始）和最大蓄水量；如果无法蓄水，则返回0，此时不返回边界。
 * 例如，当山脉为s=[3,1,2]时，则选取s[0]和s[2]作为水库边界，则蓄水量为1，此时输出：0 2:1
 * 当山脉s=[3,2,1]时，不存在合理的边界，此时输出：0。
 *
 * 输入描述
 * 一行正整数，用空格隔开，例如输入
 *
 * 1 2 3
 *
 * 表示s=[1,2,3]
 *
 * 输出描述
 * 当存在合理的水库边界时，输出左边界、空格、右边界、英文冒号、蓄水量；例如
 *
 * 0 2:1
 *
 * 当不存在合理的书库边界时，输出0；例如
 *
 * 0
 *
 * 备注
 * 1 ≤ length(s) ≤ 10000
 * 0 ≤ s[i] ≤ 10000
 */
public class Reservoir {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 读取输入
        String input = scanner.nextLine();
        scanner.close();

        List<Integer> heights = splitToIntList(input, " ");
        int n = heights.size();

        // 计算左侧最大高度
        int[] left = new int[n];
        for (int i = 1; i < n; i++) {
            left[i] = Math.max(left[i-1], heights.get(i-1));
        }
        // 计算右侧最大高度
        int[] right = new int[n];
        for (int i = n-2; i >= 0; i--) {
            right[i] = Math.max(right[i+1], heights.get(i+1));
        }

        int[] waterLine = new int[n];
        Set<Integer> waterLevels = new TreeSet<>();
        for (int i = 0; i < n; i++) {
            int water = Math.max(0, Math.min(left[i], right[i]) - heights.get(i));
            if (water > 0) {
                waterLine[i] = water + heights.get(i);
                waterLevels.add(waterLine[i]);
            }
        }

        int[] res = {0, 0, 0}; // 左边界, 右边界, 最大存水量
        for (int level : waterLevels) {
            int l = 0, r = n - 1;
            while (waterLine[l] < level || heights.get(l) >= level) l++;
            while (waterLine[r] < level || heights.get(r) >= level) r--;

            int sum = 0;
            for (int i = l; i <= r; i++) {
                sum += Math.max(0, level - heights.get(i));
            }

            if (sum > res[2] || (sum == res[2] && (r - l + 1) < (res[1] - res[0] + 1))) {
                res[0] = l - 1;
                res[1] = r + 1;
                res[2] = sum;
            }
        }

        if (res[2] == 0) {
            System.out.println("0");
        } else {
            System.out.println(res[0] + " " + res[1] + ":" + res[2]);
        }
    }

    public static List<Integer> splitToIntList(String str, String delimiter) {
        List<Integer> result = new ArrayList<>();
        for (String s : str.split(delimiter)) {
            result.add(Integer.parseInt(s));
        }
        return result;
    }
}
